typedef struct
{
	char str[MaxSize];
	int length;
}String;

int KMPIndex(String S, int start, String T, int next[])
{
	int i = start;
	int j = 0;
	int v;

	while(i < S.length && j < T.length)
	{
		if(S.str[i] == T.str[j])
		{
			i++;
			j++;
		}

		else if(j == 0) i++;
		else j = next[j];
	}

	if(j == T.length) v = i - T.length;
	else v = -1 ;
	return v;
}

void GetNext(String T, int next[])
{
	int j = 1;
	int k = 0;

	next[0] = -1;
	next[1] = 0;

	while(j < T.length)
	{
		if(T.str[j] == T.str[k])
		{
			next[j+1] = k + 1;
			j++;
			k++;
		}
		else if(k == 0)
		{
			next[j+1] = 0;
			j++;
		}
		else k = next[k];
	}
}